public class CanJump {
    // leetcode 跳跃游戏
    // https://leetcode.cn/problems/jump-game/description/?envType=study-plan-v2&envId=top-100-liked
    public boolean canJump1(int[] nums) {
        int len = nums.length;
        boolean[] dp = new boolean[len];
        dp[0] = true;
        for (int i = 1; i < len; i++) {
            for (int j = i-1; j >= 0; j--) {
                if (dp[j] && j + nums[j] >= i) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[len-1];
    }

    /**
     * 贪心
     * @param nums
     * @return
     */
    public boolean canJump(int[] nums) {
        int len = nums.length;
        int maxDistance = 0;
        for (int i = 0; i < len; i++) {
            if (maxDistance < i) return false;
            maxDistance = Math.max(maxDistance, i+nums[i]);
            if (maxDistance >= len-1) return true;
        }
        return maxDistance >= len-1;
    }

    public static void main(String[] args) {
        int[] nums = {2,3,1,1,4};
        CanJump canJump = new CanJump();
        System.out.println(canJump.canJump(nums));
    }
}
